package 中等.脑筋急转弯;

import java.util.*;

/**
 * 你是一位系统管理员，手里有一份文件夹列表 folder，你的任务是要删除该列
 * 表中的所有 子文件夹，并以 任意顺序 返回剩下的文件夹。
 * 如果文件夹 folder[i] 位于另一个文件夹 folder[j] 下，那么 folder[i] 
 * 就是 folder[j] 的 子文件夹 。
 * 文件夹的「路径」是由一个或多个按以下格式串联形成的字符串：'/' 后跟一
 * 个或者多个小写英文字母。
 * 例如，"/leetcode" 和 "/leetcode/problems" 都是有效的路径，而空字符
 * 串和 "/" 不是。
 *  
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/remove-sub-folders-from-the-filesystem
 */
public class 删除子文件夹_1233 {

    public static void main(String[] args) {

        System.out.println(removeSubfolders(new String[]{
                "/a", "/a/b", "/c/d", "/c/d/e", "/c/f"
        }));

    }


    /**
     * 1，先将目录按字典序排序，如果某个目录的前缀目录存在，必然是
     * 在之前出现过，记录每个出现的目录
     * 2，某个目前的前缀是指，/a/b/c 是 /a 和 /a/b
     */
    public static List<String> removeSubfolders(String[] folder) {
        List<String> list = new ArrayList<>();
        Arrays.sort(folder, (a, b) -> a.compareTo(b));
        Set<String> set = new HashSet<>();

        for (String s : folder) {
            if (s.lastIndexOf("/") == 0) {
                set.add(s);
                list.add(s);
                continue;
            }

            int idx = 1;
            boolean hasPrefix = false;
            while (idx < s.length()) {
                while (idx < s.length() && s.charAt(idx) != '/') {
                    idx++;
                }
                if (set.contains(s.substring(0, idx))) {
                    hasPrefix = true;
                    break;
                }
                idx++;
            }

            if (!hasPrefix) {
                list.add(s);
            }
            set.add(s);
        }

        return list;
    }

    /**
     * 字典树
     */
    public List<String> removeSubfolders2(String[] folder) {

        Trie trie = new Trie();
        for (String s : folder) {
            trie.add(s);
        }
        List<String> ans = new ArrayList<>();
        for (String s : folder) {
            if (trie.notExistPrefix(s)) {
                ans.add(s);
            }
        }

        return ans;
    }

    static class Trie {

        private Trie[] next = new Trie[27];

        private boolean isEnd;

        private void add(String str) {
            Trie curTrie = this;
            for (int i = 0; i < str.length(); i++) {
                int nextIdx = str.charAt(i) - 'a';
                if (nextIdx == -50) {
                    nextIdx = 26;
                }
                Trie nextTrie = curTrie.next[nextIdx];
                if (nextTrie == null) {
                    nextTrie = new Trie();
                    curTrie.next[nextIdx] = nextTrie;
                }
                curTrie = curTrie.next[nextIdx];
            }
            curTrie.isEnd = true;
        }

        private boolean notExistPrefix(String str) {
            Trie curTrie = this;

            for (int i = 0; i < str.length(); i++) {
                int nextIdx = str.charAt(i) - 'a';
                if (nextIdx == -50) {
                    nextIdx = 26;
                }
                if (i < str.length() - 1 && curTrie.isEnd && nextIdx == 26) {
                    return false;
                }
                curTrie = curTrie.next[nextIdx];
            }

            return true;
        }

    }

}
